Fermat's Little Theorem
Module 02 / Lesson 05
Video Tutorial
Theoretical Rule
Fermat's Little Theorem states that if p is a prime number, then for any integer a such that a is not divisible by p, the following congruence holds:
ap-1 ≡ 1 (mod p)
Key Requirements:
- p must be a prime number.
- a should not be a multiple of p (i.e., GCD(a, p) = 1).
Numerical Example:
Let a = 2 and p = 7 (7 is prime).
According to the theorem: 2(7-1) mod 7 = 26 mod 7.
26 = 64.
64 mod 7 = 1 (since 7 * 9 = 63).
Python Implementation
def check_fermat(a, p):
# a^(p-1) % p should be 1
result = pow(a, p - 1, p)
return result == 1
# Testing the theorem
p = 7
a = 2
if check_fermat(a, p):
print(f"Verified: {a}^({p}-1) mod {p} = 1")
else:
print("Condition not met (check if p is prime)")
# Application: Finding Modular Inverse
# a^(p-2) mod p is the inverse of a
inverse = pow(a, p - 2, p)
print(f"Modular inverse of {a} mod {p} is: {inverse}")